#include <stdio.h>
#include <stdlib.h>
#include <queue>
using namespace std;

/***
 * 一棵二叉树用链式存储方式表示, 求二叉树第K层的节点个数
 * 并依次输出.
 *      写出结构体
 *      写出算法
 * */

typedef int DataType;

typedef struct TNode
{
    DataType data;
    TNode *left, *right;
} * Tree, TNode;

// 递归
void GetLayerNodeNum(Tree &T, int layerNum, int layerNow)
{
    if (!T)
        return;
    if (layerNow == layerNum)
    {
        printf("%d ", T->data);
        return;
    }

    GetLayerNodeNum(T->left, layerNum, layerNow + 1);
    GetLayerNodeNum(T->right, layerNum, layerNow + 1);
}

// 递归参数会暴露较多内部参数 可以再封装一层
void GetLayerNodeNum(Tree &T, int layerNum)
{
    GetLayerNodeNum(T, layerNum, 1);
}

// 测试用
TNode *NewNode(int e)
{
    TNode *s = (TNode *)malloc(sizeof(TNode));
    s->data = e;
    s->left = NULL;
    s->right = NULL;
    return s;
}

// 层序遍历
void PrintTree(Tree T)
{
    queue<TNode *> q;
    if (T != NULL)
    {
        q.push(T);
    }
    while (!q.empty())
    {
        printf("%d ", q.front()->data);
        if (q.front()->left != NULL)
            q.push(q.front()->left);

        if (q.front()->right != NULL)
            q.push(q.front()->right);
        q.pop();
    }
}

int main()
{

    Tree T;
    T = NewNode(0);
    T->left = NewNode(1);
    T->right = NewNode(2);
    T->left->left = NewNode(3);
    T->left->right = NewNode(4);
    T->right->left = NewNode(5);

    PrintTree(T);
    printf("\n");

    GetLayerNodeNum(T, 3);

    return 0;
}